// 并查集类-->以QuickUnion算法为例
export class UnionFind {
    protected unionList: number[];
    protected initialValue: number;
    protected count: number;
    constructor(size: number) {
        // 初始化连通分量列表，初始化时每个触点仅仅链接自己
        this.unionList = new Array(size + 1).fill(-1);
        for (let i = 0; i < size; i++) {
            this.unionList[i] = i;
        }
        this.count = size + 1;
        this.initialValue = size;
    }
    // 检查输入是否合理
    protected checkInput(num: number): boolean {
        return num <= this.initialValue;
    }
    // 快速查找方法
    protected quickFind(elem: number): number {
        while (elem !== this.unionList[elem]) {
            elem = this.unionList[elem];
        }
        return elem;
    }
    // 统计连通分量个数
    getCount(): number {
        return this.count;
    }
    // 添加连接通量方法
    union(union: Union): boolean {
        const [point1, point2] = union;
        // 检查输入是否合理
        if (!this.checkInput(point1) || !this.checkInput(point2)) return false;
        // 根据两个触点位置寻找触点的终点位置
        const end1 = this.quickFind(point1);
        const end2 = this.quickFind(point2);
        // 如果两个触点的终点相同说明它们是同一个联通分量，直接返回
        if (end1 === end2) return false;
        // 否则建立新的连通分量
        this.unionList[end1] = end2;
        this.count--;
        return true;
    }
}


// 测试用例，最大值为9
const uf: UnionFind = new UnionFind(9);
uf.union([4, 3]);
uf.union([3, 8]);
uf.union([6, 5]);
uf.union([9, 4]);
uf.union([2, 1]);
uf.union([8, 9]);
uf.union([5, 0]);
uf.union([5, 0]);
uf.union([7, 2]);
uf.union([6, 1]);
uf.union([1, 0]);
uf.union([6, 7]);
console.log(uf.getCount()); // 2
uf.union([1, 8]);
console.log(uf.getCount()); // 1


